Devices such as computer terminals, phones, fax machines, etc. can transfer information such as data, voice, video, and electronic mail, etc. by means of communication networks. When devices communicate, they generate traffic that is routed over the communication network to which the devices are connected.
In a connection-oriented data network, a call setup phase establishes the route between the call origination and destination points in the network. All traffic is sent through the network on the path established in the call setup phase. During the call setup phase, bandwidth resources are reserved to route a traffic stream through the network. An important feature of contemporary connection-oriented networks, e.g. frame relay, ATM, and MPLS, is the ability to deliver services with varying rates. The traffic streams to deliver different service types, e.g. voice or video, require different amount of resources across the network. If a route cannot be found with the required amount of bandwidth then the call is blocked from accessing the network.
A network is composed of nodes (switches) and links. A link connects exactly two nodes. The traffic that enters a network is usually referred to as an ingress node and the traffic that leaves the network is usually referred to as an egress node. Hereafter, ingress and egress nodes will be referred to simply as ingress and egress. In state-of-the-art broadband data networks, either constant or variable bit rate characterizes a traffic stream. The bandwidth resources required to service a constant bit rate are straightforward. However, the bandwidth needed to service a variable bit rate traffic stream can be determined using the concept of Equivalent or Effective bandwidth. Numerous techniques have been developed to determine effective bandwidth of a variable bit rate, see for example M. Schwartz, “Broadband Integrated Networks”, Prentice Hall, 1996, and R. Guerin, H. Ahmadi, and M. Naghshineh, “Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks”, IEEE Journal on Selected Areas in Communications, Vol. 9, No. 7, 1991. Although the traffic in a data network is routed in discrete packets or frames or cells, due to the effective bandwidth concept the traffic flow can be treated as constant. Therefore, in the context of routing, a Time Division Multiplex (TDM) trunk is similar to a virtual connection in Asynchronous Transmission Mode (ATM) or a virtual circuit in frame relay or a label switch path (LSP) in Multi-Protocol Label Switching (MPLS). Hereafter, trunk will be used to refer to a virtual connection or virtual circuit or LSP.
One method addresses optimal routing but uses a technique of asymptotically determining loss probability then solves a set of linear equations to determine network sensitivity. Another system provides a method of grouping virtual circuits into virtual paths. Traffic trues consume bandwidth resources on the network links and nodes. To insure acceptable quality of service (QoS) trunks should be routed so that resources are not over-utilized. When their traffic is loaded on trunks that are routed on over-utilized links, the customers experience performance problems such as long delays and loss of data. Hence it is critically important to route trunks such a way that same bandwidth resources are not allocated to different trunks that will cause congestion in the network.
The number of trunks that can be routed over a given network greatly depends on how network resources are allocated to various trunks. Therefore, the problem of routing maximum number of trunks in a resource-constrained network can essentially be characterized as an optimal resource allocation problem. The combinatorial nature of the optimal routing requires efficient search algorithms.
Therefore, what is needed is a method and system to optimally allocate link bandwidth in a communications network.